1. Field of the Invention
This invention relates to a method for scheduling data streams and, more particularly, to a method for scheduling a packet based data stream using a slack value calculation.
2. Description of the Prior Art
In many networking arrangements, it is necessary for a plurality of data streams to be combined to share a limited number of channels or even a single line. This can happen, for example, in a wireless type network where a number of units are routed to a base station which is further connected through a single channel. Thus, the various streams going to the individual units must be handled through a single channel. Another similar situation is where various kinds of data streams, such as voice data, real time video data, email and other data are all handled through an Internet protocol network. These various different kinds of data must be combined into a limited number of channels or even a single channel for transmission.
Whenever such data streams are merged, it is necessary to have some protocol for selecting the order in which they are placed in the channel. While the simplest solution may be a first come, first serve arrangement, this may not be the most effective since some data streams are more time sensitive than others. For example, voice signals cannot be delayed very much at all, whereas email messages may be delayed by a substantial amount. Accordingly, a number of protocols have been sought to provide fair and optimum criteria for multiple users so that delay is reduced, invalid data is minimized and data throughout is maximized.
One attempt at such a scheduling method is referred to as deficit round robin where a fairness level is achieved by using a deficit counter and a quantum of service for each user flow which decides how long the flow should constantly be served before moving onto the next data flow. The maximum delay for revisiting a user is governed by the round duration in the scheduler and depends on the packet lengths and the number of flows in the system. However, this method is inefficient when lower bound delay requirements must be satisfied. This is because the packet may be delayed by a full round duration and since the maximum delay is governed by the round duration, it would be impossible to provide different delay bounds to different flows, thereby resulting in a high drop ratio of packets, that is, real time packets that exceed their delay requirements.
In a method called the weighted fair queuing, the delay in a user packet flow is decreased by increasing the allocated service rate and in another method referred to as earliest due date, each flow is served using a deadline base strategy where the user with the packet of earliest deadline waiting to be scheduled is selected first. In these two systems, the transmission of a scheduled packet must be completed before scheduling another packet. Therefore, the delay guarantees of a packet depends on the length of another packet in a different flow sharing the same channel. Thus, a new short packet arriving in the system could time out while waiting for another packet of lower sensitivity to finish transmission. This leads to lower system throughput. Another drawback of weighted fair queuing scheduling is that the number of bits served in a scheduling round is proportional to the rate allocated to the flow. To reduce the delay for a flow, its allocated rate must be set-up to a higher volume before starting service of the flow. Given that the rate is fixed throughout service of the flow, the coupling between the rate allocation and the delay may lead to inefficient resource utilization. While a low value does not provide enough quality of service, a very large rate allocation leads to a waste of bandwidth. This is due to the rate fluctuations in a real time variable bit rate traffic.